40. 组合总和 II

Similar Question

这里的跳过重复和 18. 四数之和, 15. 三数之和 的思路一致

要对结果去重很困难, 那就进行剪枝来做到去重

Solution Tips

方案一: 回溯 + 跳过重复 + 剪枝

var combinationSum2 = function (candidates, target) {
    const res = [];
    const cur = [];
    let curSum = 0;
    // 数字自身就是有重复的, 数组本身不能去重, 但是却要对最后的结果进行去重
    candidates.sort((a, b) => a - b);

    function backTracking(curIndex) {
        if (curSum === target) {
            res.push([...cur])
            return;
        }

		if (curSum > target) {
			return;
		}

        // 剪枝, 可以考虑升序排序然后剪枝
        for (let i = curIndex; i < candidates.length; i++) {
            cur.push(candidates[i]);
            curSum += candidates[i];

            backTracking(i + 1);
            // 回溯操作
            cur.pop();
            curSum -= candidates[i];
            // 在这里去重, index 要从一个新的数字开始 这个去重操作, 似成相识
			// 完美的做到了同层级去重, 却不影响 dfs 获取相同的 num, 其他人还是没有融会贯通呀
            while (candidates[i] === candidates[i + 1]) i++;
        }
    }

    backTracking(0);
    return res;
};
let candidates = [2, 3, 6, 7], target = 7
console.log(combinationSum2(candidates, target));